package 剑指专题.动态规划;


/*
 * Author：江松
 * Date：2023/3/20 20:47
 */

public class Main2 {
    public int[] FindGreatestSumOfSubArray (int[] array) {
        // write code here
        int dp=0,ans=Integer.MIN_VALUE;
        //记录每次子序列的边界和大小
        int left=0,size=0;
        //记录最佳子序列
        int mleft=-1,msize=0;
        for(int i=0;i<array.length;++i){
            if(dp>=0){
                dp+=array[i];
                size++;
            }else{
                dp=array[i];
                left=i;
                size=1;
            }

            if(ans<=dp){
                if(ans==dp){
                    //如果都是一个值，那么取最长的
                    if(msize<size){
                        msize=size;
                        mleft=left;
                    }
                }else{
                    //取最大情况的边界和大小
                    ans=dp;
                    msize=size;
                    mleft=left;
                }

            }
        }

        int res[]=new int[msize];
        for(int i=0;i<msize;++i){
            res[i]=array[i+mleft];
        }
        return res;
    }
}
